package demo1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //最小反转次数是二进制矩阵回文 2
    public int minFlips(int[][] grid) {
        int n = grid.length, m = grid[0].length, res = 0;
        for (int i=0; i<m/2; i++) {
            int l = i, r = m-i-1;
            for (int j=0; j<n/2; j++) {
                int[] ans = {0, 0};
                ans[grid[j][l]]++;
                ans[grid[n-j-1][l]]++;
                ans[grid[j][r]]++;
                ans[grid[n-j-1][r]]++;
                res += Math.min(ans[0], ans[1]);
            }
        }
        int[] ans = {0, 0, 0};
        if ((n & 1) == 1) {
            for (int i=0; i<m/2; i++) {
                ans[grid[n/2][i] + grid[n/2][m-i-1]]++;
            }
        }
        if ((m & 1) == 1) {
            for (int i=0; i<n/2; i++) {
                ans[grid[i][m/2] + grid[n-i-1][m/2]]++;
            }
        }
        if ((m & n & 1) == 1) res += grid[n/2][m/2];
        res += ans[1];
        if (ans[1] == 0 && (ans[2] & 1) == 1) res += 2;
        return res;
    }

    //两数相加 2
//    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        ListNode h1 = l1;
//        int size1 = 0;
//        ListNode h2 = l2;
//        int size2 = 0;
//        while (h1 != null) {
//            h1 = h1.next;
//            size1++;
//        }
//        while (h2 != null) {
//            h2 = h2.next;
//            size2++;
//        }
//
//    }


    //计算右侧小于当前元素的个数
    int[] ret;
    int[] index;
    int[] tmp;
    int[] tmpindex;
    public List<Integer> countSmaller(int[] nums) {
        ret = new int[nums.length];
        index = new int[nums.length];
        tmp = new int[nums.length];
        tmpindex = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            index[i] = i;
        }
        mergeSort(nums,0,nums.length-1);
        List<Integer> retlist = new ArrayList<>();
        for(int each:ret)
            retlist.add(each);
        return retlist;
    }

    private void mergeSort(int[] nums,int left,int right){
        if(left>=right) return ;
        int mid = (left+right)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);

        int pcur1 = left; int pcur2 = mid+1; int key = 0; int j = 0;
        while (pcur1 <= mid && pcur2 <= right) {
            if(nums[pcur1]<=nums[pcur2]){
                tmpindex[j] = index[pcur2];
                tmp[j++] = nums[pcur2++];
            }else {
                key += right - pcur2 +1;
                ret[index[pcur1]] += key;
                tmpindex[j] = index[pcur1];
                tmp[j++] = nums[pcur1++];
            }
        }
        while(pcur1<=mid){
            tmpindex[j] = index[pcur1];
            tmp[j++] = nums[pcur1++];
        }
        while(pcur2<=right){
            tmpindex[j] = index[pcur2];
            tmp[j++] = nums[pcur2++];
        }
        for (int i = left; i <= right; i++) {
            nums[i] = tmp[i-left];
            index[i] = tmpindex[i-left];
        }
    }


}

























